package com.clps.algorithm.chapter08.二叉搜索树中两个结点之和;

import com.clps.algorithm.chapter07.二叉树每层的最大值.TreeNode;

import java.util.Stack;

/**
 * 给你一个二叉搜索树和一个值k，请判断该二叉搜索树中是否存在两个结点它们的值之和等于k。假设二叉搜索树中结点的值均唯一。
 * 例如在图8.12中的二叉搜索树里，存在两个两个结点它们的和等于12（结点5和结点7），但不存在两个结点值之和为22的结点。
 */
public class BSTIterator {

    TreeNode cur;
    Stack<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        cur = root;
        stack = new Stack<>();
    }

    public boolean hasNext(){
        return  cur!=null || !stack.isEmpty();
    }

    public int next(){
        while (cur!=null){
            stack.push(cur);
            cur =cur.left;
        }
        cur= stack.pop();
        int val = cur.val;
        cur = cur.right;
        return  val;
    }


}


